//输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 
//
// 
//
// 参考以下这颗二叉搜索树： 
//
//      5
//    / \
//   2   6
//  / \
// 1   3 
//
// 示例 1： 
//
// 输入: [1,6,3,2,5]
//输出: false 
//
// 示例 2： 
//
// 输入: [1,3,2,6,5]
//输出: true 
//
// 
//
// 提示： 
//
// 
// 数组长度 <= 1000 
// 
// Related Topics 栈 树 二叉搜索树 递归 二叉树 单调栈 👍 531 👎 0

package leetcode.editor.cn;
//leetcode submit region begin(Prohibit modification and deletion)
class SolutionOffer33 {
    public boolean verifyPostorder(int[] postorder) {
        return traversal(postorder, 0, postorder.length-1);
    }

    public boolean traversal(int[] postorder, int i, int j){
        if(i >= j) return true;
        int root = postorder[j];
        int delimiter = j; //分成左右两部分：[i,delimiter-1],[delimiter,j-1]
        for(int k = i; k <= j; k++){
            if(postorder[k] > root){
                delimiter = k;
                break;
            }
        }
        //左子树第一个for已经全部小于root,继续判断右子树所有元素是否小于root
        for(int k = delimiter; k < j; k++){
            if(postorder[k] < root){
                return false;
            }
        }
        return traversal(postorder,i,delimiter-1) && traversal(postorder,delimiter,j-1);
    }

    public static void main(String[] args) {
        new SolutionOffer33().verifyPostorder(new int[]{4, 6,7,5});
    }
}
//leetcode submit region end(Prohibit modification and deletion)
